package cn.pugle.oj.leetcode;

import cn.pugle.oj.catalog.GraphProblem;
import cn.pugle.oj.catalog.Unknown;

import java.util.*;
import java.util.stream.Collectors;

/**
 * 并查集变种, 秀
 *
 * @author tzp
 * @since 2020/11/3
 */
public class LC399 extends LC547_1 implements GraphProblem {
    static class UF {
        Map<String, String> parent = new HashMap<>();
        Map<String, Double> result = new HashMap<>();
        Map<String, Integer> rank = new HashMap<>();


        public UF() {
        }

        public String find(String i) {
            if (!parent.containsKey(i)) return null;
            while (!parent.get(i).equals(i)) {
                Double p = result.get(i);
                Double pp = result.get(parent.get(i));
                result.put(i, p * pp);
                parent.put(i, parent.get(parent.get(i)));//find的时候进行压缩path

                i = parent.get(i);
            }
            return i;
        }

        public Double result(String i) {
            if (!result.containsKey(i)) return null;
            return result.get(i);
        }

        private void init(String i) {
            if (!parent.containsKey(i)) {
                parent.put(i, i);
                result.put(i, 1.0);
                rank.put(i, 1);
            }
        }

        public boolean union(String x, String y, double value) {//a / b = 2
            init(x);
            init(y);
            String xp = find(x);
            String yp = find(y);
            if (xp.equals(yp)) return false;
            if (rank.get(xp) < rank.get(yp)) {//xprank小, 把xp接到yp下面
                parent.put(xp, yp);
                //已知 x/y=value, x/xp, y/yp 求xp/yp
                Double x_xp = result.get(x);
                Double y_yp = result.get(y);
                result.put(xp, value / x_xp * y_yp);
            } else if (rank.get(xp) > rank.get(yp)) {
                parent.put(yp, xp);
                //已知 x/y=value, x/xp, y/yp 求yp/xp
                Double x_xp = result.get(x);
                Double y_yp = result.get(y);
                result.put(yp, x_xp / value / y_yp);
            } else {//==, rank+1
                parent.put(xp, yp);
                //已知 x/y=value, x/xp, y/yp 求xp/yp
                Double x_xp = result.get(x);
                Double y_yp = result.get(y);
                result.put(xp, value / x_xp * y_yp);

                rank.put(yp, rank.get(yp) + 1);
            }
            return true;
        }
    }

    public double[] calcEquation(List<List<String>> equations, double[] values, List<List<String>> queries) {
        UF uf = new UF();
        for (int i = 0; i < equations.size(); i++) {
            List<String> equation = equations.get(i);
            uf.union(equation.get(0), equation.get(1), values[i]);
        }
        double[] rs = new double[queries.size()];
        for (int i = 0; i < queries.size(); i++) {
            List<String> query = queries.get(i);
            String p0 = uf.find(query.get(0));
            String p1 = uf.find(query.get(1));
            if (p0 == null || p1 == null || !p0.equals(p1)) {
                rs[i] = -1;
            } else {
                Double r0 = uf.result(query.get(0));
                Double r1 = uf.result(query.get(1));
                rs[i] = r0 / r1;
            }
        }
        return rs;
    }

    public static void main(String[] args) {
//        String[][] a = {{"a", "b"}, {"b", "c"}};
//        double[] b = {2.0, 3.0};
//        String[][] c = {{"a", "c"}, {"b", "a"}, {"a", "e"}, {"a", "a"}, {"x", "x"}};
//        String[][] a = {{"x1", "x2"}, {"x2", "x3"}, {"x3", "x4"}, {"x4", "x5"}};
//        double[] b = {3.0, 4.0, 5.0, 6.0};
//        String[][] c = {{"x1", "x5"}, {"x5", "x2"}, {"x2", "x4"}, {"x2", "x2"}, {"x2", "x9"}, {"x9", "x9"}};
        String[][] a = {{"a", "b"}, {"e", "f"}, {"b", "e"}};
        double[] b = {3.4, 1.4, 2.3};
        String[][] c = {{"a", "c"}, {"b", "a"}, {"a", "e"}, {"a", "a"}, {"x", "x"}};
        System.out.println(Arrays.toString(new LC399().calcEquation(
                twoDArrayToList(a), b, twoDArrayToList(c))));
    }

    public static List<List<String>> twoDArrayToList(String[][] twoDArray) {
        return Arrays.stream(twoDArray)
                .map(Arrays::asList)
                .collect(Collectors.toList());
    }
}
